In the field of digital data storage, data reliability is critical. Specifically, it is important that the user data that are retrieved from a medium match the data that were written to and stored on the medium. For a variety of reasons, the retrieved data may differ from the data that were originally stored. Any differences between the stored data and the retrieved data are considered errors in the data. Traditional methods for ensuring data reliability have included error detection and error correction. Typical error detection and correction techniques involve appending parity bits to the data during an encoding process to form a codeword prior to storage. When the codeword (data with parity bits) is later retrieved from the medium, it is decoded, and the parity bits are used to detect and correct errors. Essentially, the parity symbols provide redundancy, which may be used to check that the data were read correctly from the medium.
Digital data is typically partitioned into a number of symbols, each consisting of a fixed number of bits. For example, in the field of data storage, 8-bit symbols or “bytes” are commonly used. An m-bit symbol may be viewed as an element of a Galois field GF(2m), which is a finite field having unique mathematical properties. By treating the data as Galois field elements, mathematical operations may be performed on the symbols in a data storage device to reach useful results, including checking for errors. Error detection and correction algorithms, such as those used with the well-known Reed Solomon (RS) codes, take advantage of the mathematical properties of Galois fields. An error correction algorithm is able to correct up to a maximum number of symbol errors. The maximum number of symbol errors that the algorithm can correct is referred to as the “correction power” of the code. Error correction algorithms are able to correct errors primarily because a limited number of data blocks constitute the valid codewords that may be stored on the medium.
Typically, before user data is stored, it is first encoded with parity symbols for the sole purpose of error detection. These parity symbols are computed from the user data and the block of data consisting of the user data and the parity symbols forms a codeword in an error detection code (EDC). The parity symbols are referred to as EDC parity and the block of data together with its EDC parity is referred to as an EDC codeword.
In addition, the data and EDC parity may be encoded with additional parity symbols for the purpose of error correction. These parity symbols are computed from the user data and EDC parity and the block of data (including the user data, the EDC parity, and the additional parity symbols) to form a codeword in an error correction code (ECC). The additional parity symbols are referred to as ECC parity. The entire block of data together with its EDC parity and ECC parity is referred to as an ECC codeword.
Over the past 55 years, several classes of ECCs have been devised and are used widely in practice, examples of which include Hamming codes, convolutional codes, Bose Chaudhuri and Hocquenghem (BCH) codes, and Reed Solomon codes. For many classes of codes, such as the RS codes, the code symbols are viewed as elements of a Galois field and the codeword is viewed as a polynomial whose coefficients are the Galois field elements. The defining property of the code is that certain values of these polynomials are equal to zero. These codes are called “polynomial codes”.
Recently, there has been a lot of interest in two other classes of ECC codes, namely, turbo codes and low density parity check (LDPC) codes. These codes and their variations which have sparse parity check matrices show appealing performance when decoded using an iterative message passing decoding algorithm. This decoding algorithm is also sometimes referred to as belief propagation. However, high rate LDPC or turbo codes of reasonable length usually exhibit an undesirable error floor in the high signal-to-noise (SNR) region due to their small minimum distance. Several research works have focused on the analysis of the error floor and the design of good codes with low error floors. In certain applications, when extremely low error rate is desired, codes with large minimum distances are still favorable. Therefore, in such applications (e.g. magnetic recording systems), Reed Solomon (RS) codes are employed due to their large minimum distances. RS codes are also widely used in many existing standards, such as optical recording, media transmission and satellite communication systems.
An optimal error correction algorithm applies a minimum distance rule, in which a block of data containing errors (an “invalid” or “corrupted” codeword) is changed to the “closest” valid codeword. This is referred to as “maximum likelihood decoding” because the decoder picks the codeword that is most likely to have resulted in the received sequence. However, for several classes of codes, such as for example RS codes, maximum likelihood decoding is computationally very complex and suboptimal decoders are normally used. A popular decoder is the Berlekamp Massey (BM) decoder which can be implemented in hardware efficiently. One of the major drawbacks of the BM decoder is that it is a hard decision decoder (HDD). That is, the received signal has to be quantized into one bit (zero or one) before it can be decoded. It is also possible to declare some bits as being ‘erased’ in addition to the one bit quantization, and such decoding is known as errors and erasure correcting. Although this is better than the HDD, it is still not as good as using many levels of quantization (possibly infinite). Such a decoder which uses many levels of quantization of the received signal is referred to as a soft decision decoder (SDD). It is commonly believed that a soft decision decoder provides nearly 2 to 3 dB gain over a hard decision decoder on an additive white Gaussian noise channel. Consequently, soft decision decoding of RS codes is of major theoretical and practical interest. In addition to being able to accept soft decisions, it is almost as important for the decoder to deliver soft outputs. This is particularly useful in concatenated systems where many decoders exchange information between them using the turbo principle. In such systems, the ability of the decoder to deliver good soft output greatly improves the overall performance. Examples of such systems include turbo equalization, turbo demodulation, and turbo multiuser detection.
A few soft input soft output (SISO) RS code decoding methods are available in the literature, which can work for either short codes or codes with small minimum distances. Most of the currently popular soft decision decoding methods are list-decoding based soft input hard output (SIHO) algorithms, which include: enhanced algebraic hard decision decoding algorithm, such as, Chase decoding and generalized minimum distance (GMD) decoding, reliability based ordered statistics decoding (OSD) (and its variation: box and match (BMA) decoding) and more recently, the Koetter-Vardy (KV) decoding algorithm, which is an algebraic SIHO decoding algorithm. All these list-decoding based SIHO algorithms can improve the performance of RS codes over additive white Gaussian noise (AWGN) channels, but can be very complex computationally. When the computational complexity is limited, the performance improvement is only marginal and, hence, they do not achieve a good performance-complexity trade-off. Further, the generation of soft outputs involves averaging over all returned codewords in the list. Consequently, the list-decoder either generates too few codewords (e.g., Chase, GMD and KV) such that the soft outputs are unreliable (or doesn't contribute at all if no codeword is returned) or outputs too many codewords (e.g., OSD) such that averaging over the whole codeword list is computationally unaffordable.
An alternate approach to algebraic soft decoding is belief propagation (BP) based iterative decoding. Iterative decoding of linear block codes using the sum product algorithm (SPA) has been described by others. It is commonly believed that BP algorithms are not suitable for high density parity check codes (HDPC), such as RS codes, since the large number of short cycles in the Tanner graph will cause correlation between unreliable messages and consequently incur “error propagation”.
Therefore, there is a need for a soft decision decoding technique for block codes such as RS codes that overcomes the limitations of previous techniques and provides good quality soft outputs.